The advent of the digital age has made large-scale data acquisition and online processing a crucial component of modern systems. A data stream management system (DSMS) is a system that enables applications to issue long-running continuous queries (CQs) that efficiently monitor and process streams of data in realtime. Data stream systems are used for data processing in a broad range of applications including clickstream analysis, fraud detection, monitoring RFID (radio-frequency identification) readings from sensors (e.g., for manufacturing and inventory control), and algorithmic trading of stocks, for example.
A class of CQs that have recently garnered significant attention is pattern CQs, where the user is interested in detecting patterns across time in a data stream. For instance, given a realtime stock quote stream, it may be desirable to detect when a stock price increases. While this simple pattern can be detected using existing mechanisms such as self-joins over windowed streams, more complex patterns involving unbounded looping operations are not expressible using standard DSMS operators. Existing pattern-detection techniques for DSMSs impose restrictions on expressiveness or on input stream ordering (or both) that make such techniques inadequate for modern stream applications.